package com.practice.niuke.new_direct_basics.class12;

import java.util.LinkedList;

/**
 * 【题目】
 * 有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边， 窗口每次 向右边滑
 * 一个位置。
 * 例如， 数组为[4,3,5,4,3,3,6,7]， 窗口大小为3时:
 * [4 3 5]4 3 3 6 7
 * 4[3 5 4]3 3 6 7
 * 4 3[5 4 3]3 6 7
 * 4 3 5[4 3 3]6 7
 * 4 3 5 4[3 3 6]7
 * 4 3 5 4 3[3 6 7]
 * 窗口中最大值为5 窗口中最大值为5 窗口中最大值为5 窗口中最大值为4 窗口中最大值为6
 * 窗口中最大值为7
 * 如果数组长度为n， 窗口大小为w， 则一共产生n-w+1个窗口的最大值。
 * 请实现一个函数。 输入:整型数组arr， 窗口大小为w。
 * 输出:一个长度为n-w+1的数组res， res[i]表示每一种窗口状态下的 以本题为例， 结果应该
 * 返回{5,5,5,4,6,7}。
 */
public class Code01_SlidingWindowMaxArray {

    /**
     * “滑动窗口算法”原型
     */
    public static class WindowMax {
        private int L;
        private int R;
        // 原数组
        private int[] arr; // arr[   [L..R)     ]
        // 滑动窗口，一个双端队列（维护一个最大值的更新结构的双端队列）
        private LinkedList<Integer> qmax;

        /**
         * 初始化滑动窗口
         *
         * @param a 原数组
         */
        public WindowMax(int[] a) {
            arr = a;
            // a[L... R)也就是a[L...R-1] 为 逻辑上的 窗口区域
            L = -1;
            R = 0;
            // 维护一个最大值的更新结构的双端队列
            qmax = new LinkedList<>();
        }

        //L = -1
        // R = 0
        // arr   [-1,1)
        //[ 3,2,1,4,5   ]
        // 0
        // [0,1)  arr[0]
        // 1
        // [-1,2)  arr[0,1]
        /**
         * “滑动窗口算法”原型中，R向右移动时的更新策略
         */
        public void addNumFromRight() {
            if (R == arr.length) {
                return;
            }
            while (
                    // 队列不为空
                    !qmax.isEmpty()
                            &&
                    // 队列最左侧的位置在原数组中的值 <= 原数组中R位置的值
                    arr[qmax.peekLast()] <= arr[R]
            ) {
                // 从右弹出，丢弃
                qmax.pollLast();
            }
            // 从右进，加入窗口
            qmax.addLast(R);
            // 最后才 R++
            R++;
        }

        // arr  [L,R)
        /**
         * “滑动窗口算法”原型中，L向右移动时的更新策略
         */
        public void removeNumFromLeft() {
            if (L >= R - 1) {
                return;
            }
            // 一开始就 L++
            L++;
            // L++后表示，L=L+1位置是要从"逻辑上的滑动窗口"左边丢弃的位置，
            // 如果此时 窗口最左侧的值代表位置 刚好是L=L+1这个位置，
            // 就从窗口左侧弹出这个位置。
            if (qmax.peekFirst() == L) {
                qmax.pollFirst();
            }
        }

        /**
         * 获取窗口中的最大值
         *
         * @return Integer
         */
        public Integer getMax() {
            if (!qmax.isEmpty()) {
                return arr[qmax.peekFirst()];
            }
            return null;
        }
    }

    /**
     * 先形成窗口大小为w的窗口后，以后没一次让R往右动一下，再让L往右动一下。
     *
     * @param arr 源数组
     * @param w   窗口的大小
     * @return
     */
    public static int[] getMaxWindow(int[] arr, int w) {
        if (arr == null || w < 1 || arr.length < w) {
            return null;
        }
        // 滑动窗口，双端队列，维护一个最大值的更新结构，
        // 双端队列里面存原数组的下标（位置）， 下标所对应的源数组中的值 由   大 -> 小
        LinkedList<Integer> qmax = new LinkedList<Integer>();
        // 每次滑动收集的答案，需要收集 arr.length - w + 1 个答案。
        int[] res = new int[arr.length - w + 1];
        int index = 0;
        // i代表，原数组中当前i位置的值进入窗口（逻辑上的窗口），i位置就是R位置
        for (int i = 0; i < arr.length; i++) { // 窗口（刚才讲的）的R
            // i -> arr[i]
            while (
                    // 队列不为空
                    !qmax.isEmpty()
                            &&
                    // 队列最左侧的位置在原数组中的值 <= 原数组中R位置的值
                    arr[qmax.peekLast()] <= arr[i]
            ) {
                // 从右弹出，丢弃
                qmax.pollLast();
            }
            // 从右进，加入窗口
            qmax.addLast(i);
            // i >= w - 1 “逻辑上的”大小为w的窗口才形成，这段逻辑才生效，
            // i - w表示L++后，L=L+1位置是要从"逻辑上的滑动窗口"左边丢弃的位置，
            // 如果此时 窗口最左侧的值代表位置 刚好是L=L+1这个位置，
            // 就从窗口左侧弹出这个位置。
            if (qmax.peekFirst() == i - w) { // i - w  过期的下标
                qmax.pollFirst();
            }
            if (i >= w - 1) { // “逻辑上的”窗口形成了
                res[index++] = arr[qmax.peekFirst()];
            }
        }
        return res;
    }

    // for test
    public static void printArray(int[] arr) {
        for (int i = 0; i != arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {4, 3, 5, 4, 3, 3, 6, 7};
        int w = 3;
        printArray(getMaxWindow(arr, w));

    }

}
